The present invention relates to image processing methods and apparatus used, for example, for an automatic mailing address reader, and in particular to image processing methods and apparatus that extract an irregular character string, such as an address that has been handwritten in Japanese.
The postal service system, for example, daily must process a large amount of mail within a short period of time. And thus, since until recently all mail had to be sorted visually and manually, the size of the work load borne by postal service employees has been very large. To reduce this work load, mechanization, represented by automatic readers, has been introduced, and this has led to the development of an advanced procedure whereby mail to be delivered is sorted by district. This way of handling mail has been successful in Japan because postal codes are entered in boxes provided for them on mailing matter; however, for overseas mail, for which no clearly defined spaces for postal code entries are provided, it is difficult to mechanically determine where on mailing matter postal codes are located. Moreover, since it is anticipated that the amount of overseas mail processed will continually increase, currently a demand exists for the continued development of present techniques to permit the immediate reading of address information, including postal codes, carried by mail, and for sorting the mail for delivery by districts.
Although there is a strong demand for the extraction of postal codes carried by mailing matter for which postal code entry areas are not defined, and for the reading of address information, it is difficult to use current techniques for these purposes. This is primarily because on the exterior surfaces of the various items that constitute the mail, not only are there areas provided for recipient addresses, but there may be other areas in which sender addresses are entered, areas in which advertising material is presented, and areas in which various patterns, such as drawings and photographs, are displayed. Further compounding the problem are the many ways in which entries are made, including the use of handwritten and mechanically printed characters, and of vertical and horizontal writing styles. As a result, in order to correctly separate postal codes and other address data from the various coexisting information entries carried by the mail, a very complicated process must be employed, such as one that provides for the examination of all external surfaces. For addresses that have been handwritten in Japanese, in particular, not only does a problem exist because both vertical and horizontal writing styles are used, but there is a further problem in that the handwritten characters used in the addresses are irregularly shaped, which makes the extraction of appropriate addresses especially difficult.
Of the conventional methods that are used to extract address information, techniques exist by which address areas and actual addresses can be identified and read. Included is a method whereby it is presumed that labels bearing printed addresses are attached to mail. For this method the reflection attributes of the labels, or the shadows thrown by the edges of the labels, are detected and the address areas are thereafter extracted. There is also a method whereby horizontal and vertical projections of the mail are obtained and are used to select probable address areas, in which zones containing high entry densities are defined as character rows. In addition, in Japanese Unexamined Patent Publication No. Hei 7-265807, a technique is disclosed whereby to extract character rows, connected components that are near each other are joined together, and the character rows are later combined to define probable address areas.
However, when addresses are printed directly on external surfaces, the method whereby address areas are extracted from accompanying entries by presuming that printed address labels are attached to mail is definitely useless. According to this method, the available mail types are very limited. And it is particularly difficult to apply this technique for addresses that are handwritten in Japanese, since in this case, labels are seldom used. Also, with the method used to select probable mailing address areas by defining as character rows zones having high entry densities, it is difficult to separate address areas from their backgrounds if the backgrounds contain large numbers of image data, and if complicated patterns are displayed on the mail. As a result, with this method correct address areas can not precisely be detected.
Especially when the technique disclosed in Japanese Unexamined Patent Publication No. Hei 7-265807 is used, it is presumed that comparatively characters are regularly aligned, and that character strings are arranged relatively near each other. Thus, although this technique can more or less be applied for printed addresses, satisfactory results can not be expected when the technique is used for irregular handwritten addresses. Furthermore, according to this technique, a complicated joining process must be performed for all pixels, i.e., portions from which pixels are accumulated are detected by examining all pixels, and this detailed examination must be repeated for each portion involved. As a result, logic operations are very difficult, processing speeds are greatly reduced, and configurations are much too complicated. Therefore, as a system configuration, this method is not realistic.
It is, therefore, one object of the present invention to avoid the use of a complicated process to combine pixels, and to quickly and precisely extract character strings such as are contained in handwritten addresses.
It is another object of the present invention to extract character strings that are irregularly arranged but that practically can be assumed to constitute an address.
It is an additional object of the present invention to extract character strings by employing a flexible and simple process for mail images, such as ones whereon vertical and horizontal writing styles coexist.
It is a further object of the present invention to employ different algorithms for regularly arranged character strings, such as printed character strings, and for irregularly arranged character strings, such as addresses that are handwritten in Japanese, so as to flexibly and accurately extract character strings.
To achieve the above and other objects, according to the present invention, a character string extraction method comprises the steps of: extracting connected components from an input image; comparing the sizes of the connected components with a predetermined threshold size, and extracting connected components occupying a range within the predetermined threshold size; extending vertically or horizontally the extracted connected components occupying a range within the predetermined threshold size, and connecting the extended connected components to form and extract long connected components; and extracting probable character strings based on the connection state of the extracted long connected components.
The step for extracting the connected components can be a method whereby an 8-connected component arranged vertically, horizontally or obliquely, or a 4-connected component arranged vertically or horizontally, is employed to extract connected components occupying a range within a predetermined threshold size.
At the step for extracting the connected components occupying a range within the predetermined threshold size, the connected components occupying the range within the predetermined threshold size may be extracted by comparing the vertical and/or horizontal size of the connected components with a predetermined vertical and/or horizontal size for an assumed character. According to this method, since the comparison is performed by defining a threshold value while taking into account the size of a handwritten character and an assumed character size, the connected components can be detected, while noise is removed from mail whereon patterns coexist. More specifically, if the height and/or width of a connected component is equal to or smaller than a first constant value (e.g., 110 points at a reduced resolution of four lines/millimeter), it can be ascertained that the pertinent connected component occupies a range within the threshold size.
It is preferable that, at the step of extracting the long connected components, the size to be extended be changed based on the size of the connected components occupying a range within the predetermined threshold size, so that the long connected components can be extracted. Thus, this process can cope with the sizes of a variety of handwritten characters. More specifically, if L is the length used to extend the connected components occupying a range within the threshold size, the pertinent connected components can at either end be extended a distance equal to the length L.
In addition, it is preferable that, at the step of extracting the long connected components, the horizontal size of the connected components occupying a range within the predetermined threshold size be reduced when the vertical size is extended, and that the vertical sizes of the connected components occupying a range within the predetermined threshold size be reduced when the horizontal size is extended, so that the long connected components can be extracted. Thus, character strings can be extracted while contact between adjacent character strings is avoided.
Furthermore, it is preferable that at the step of extracting the long connected components the size to be reduced be changed based on the size of the extracted connected components that occupy a range within the threshold size. As a result, as is described above, this process can cope with handwritten characters having a variety of sizes.
The character string extraction method further comprises the steps of: dividing the input image into segments while assuming that the segments are mesh images having a predetermined size, and setting to the ON state the mesh images that correspond to the connected components that occupy a range within the predetermined threshold size that is extracted; and extracting the contents of a specific area from the connection state of mesh images that are in the ON state.
In addition, the character string extraction method further comprises: shifting to the step of setting the mesh image to the ON state when the image represents an address composed of printed characters; and shifting to the step of extracting the long connected components when the image represents an address composed of handwritten characters. As a result, a simpler area extraction method can be used for an area containing an address consisting of printed characters, and the processing speed can be increased.
The method for which the mesh images are employed to extract the contents of a specific area is a method that involves the changing to meshes of pixel units constituting areas having a predetermined quadrilateral size, and the simplification of the meshes by regarding each of them as a single point. Thus, compared with a conventional system, an address area can be quickly detected by using a simple algorithm.
Also, to achieve the above objects, a character string extraction method according to the present invention comprises the steps of: extracting connected components having a predetermined size from an input image in which handwritten characters are included; extending the connected components in one direction and reducing the connected components in the other direction in order to assume a string exists that has a plurality of characters; detecting the state of the string of characters that is assumed; and inferring an address pattern from the state of the string of characters that is detected.
It is preferable that the state of the string of characters indicate the length and the raised and recessed condition of the string, and that a high priority for the performance of character recognition be given to a string that is long and has few raised and recessed portions. As a result, a more appropriate character string can be extracted that qualifies as a probable address character string.
Further, the vertical or the horizontal size of the connected components is extended at a predetermined ratio, while the other size is reduced at a predetermined ratio, and the connection state of the connected components that are extended and reduced is employed to assume the existence of the string of characters.
Furthermore, to achieve the above and other objects, a character string extraction apparatus according to the present invention comprises: a connected component detector for detecting, in a binary image, connected components consisting of black pixels; a character-sized connected component extraction unit for extracting character-sized connected components having an appropriate size from the connected components detected by the connected component detector; a connected component extension/reduction unit for extending, in an assumed character string direction, the character-sized connected components extracted by the character-sized connected component extraction unit, and for reducing the character-sized connected components in a direction perpendicular to the assumed character string direction; a long connected component extraction unit for connecting, in the assumed character string direction, a plurality of the connected components obtained by the connected component extension/reduction unit, and for extracting a long connected component; and a character string selector for employing the long connected component extracted by the long connected component extraction unit to determine a character string for image recognition.
And in addition, it is preferable that the character-sized connected component extraction unit extract the character-sized connected components based on a threshold value, which is defined while taking into consideration the size of the handwritten characters inscribed on the mail.
The assumed character string direction is vertical when the character string under consideration is a vertically written address, or is horizontal when the character string under consideration is a horizontally written address.
Further, to achieve the above and other objects, an image processing apparatus according to the present invention comprises: image input means for entering an image; a connected component extraction means for extracting from the image connected components, entered using the image input means, having a predetermined size; long vertical connected component generation means for vertically extending and horizontally reducing the connected components extracted by the connected component extraction means to obtain long vertical connected components; long horizontal connected component generation means for horizontally extending and vertically reducing the connected components extracted by the connected component extraction means to obtain long horizontal connected components; long connected component extraction means for vertically connecting a plurality of the long vertical connected components obtained by the long vertical connected component generation means, and for horizontally connecting a plurality of the long horizontal connected components obtained by the long horizontal connected component generation means to extract long connected components; probable character string extraction means for extracting probable character strings based on the long connected components that are extracted by the long connected component extraction means; and image recognition means for performing image recognition for the probable character strings that are extracted by the probable character string extraction means.
From among the long connected components extracted by the long connected component extraction means, the probable character string extraction means outputs a longer connected component for which a higher priority is provided.
It is preferable that, to determine a priority, the probable character string extraction means reduce evaluation scores for connected components where the long vertical connected components and the long horizontal connected components intersect. Thus, an image processing apparatus can be provided that avoids the extraction of a false character string and that is superior for practical use.
These and other objects, features and advantages of the present invention will become apparent from the following detailed description of illustrative embodiments thereof, which is to be read in connection with the accompanying drawings.